package twobranchTree.connectright2;

import twobranchTree.connectright.Node;

/**
 * @Date 2020/03/04
 * @author 王光浩
 * @Thinking 使用递归+前序遍历的方式实现。
 */
public class MyMethodTwo {
	public Node connect(Node root) {
		recursively(root);
		return root;
	}
	/**
	 * 进行前序遍历，然后在遍历的过程中将每层节点依次进行连接
	 * @param root the root of subtree
	 */
	private void recursively(Node root) {
		if(root==null)return;
		if(root.left==null && root.right==null)return ;  //叶子节点
		//将root的左右直接子节点相互连接，同时将直接子节点与同层的下一个节点进行连接
		if(root.left!=null && root.right!=null)
			root.left.next=root.right;
		Node tem=root.right!=null?root.right:root.left;
		Node next=root.next;
		while(next!=null) {
			if(next.left!=null || next.right!=null)
				break;
			next=next.next;
		}
		if(next!=null)  //将同层的两个子树相互连接
			tem.next=next.left!=null?next.left:next.right;
		//进行前序遍历
		recursively(root.left);
		recursively(root.right);
	}
}
